package pers.vic.basics.leetcode;

import com.sun.org.apache.bcel.internal.generic.RETURN;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Vic.xu
 * @description: 19. 删除链表的倒数第N个节点
 * @date: 2020/11/11  8:56
 */
public class J0019_M_removeNthFromEnd {

    /*
    给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
    给定一个链表: 1->2->3->4->5, 和 n = 2.
    当删除了倒数第二个节点后，链表变为 1->2->3->5.
     */

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        int num = 0;
        ListNode cur = head;
        Map<Integer, ListNode> map = new HashMap<>();
        while (cur != null) {

            map.put(num++, cur);
            cur = cur.next;
        }
        int key = num - n;
        if (key < 0) {
            return head;
        }
        ListNode removed = map.get(key);
        ListNode pref = map.get(key - 1);
        ListNode next = map.get(key + 1);
        //删除后 没有前后节点
        if (pref == null && next == null) {
            return null;
        }

        //没有前节点 但是有后置节点
        if (pref == null && next != null) {
            return next;
        }
        if (pref != null && next == null) {
            pref.next = null;
        }

        if (pref != null && next != null) {
            pref.next = next;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode five = new ListNode(5);
        ListNode four = new ListNode(4, five);
        ListNode three = new ListNode(3, four);
        ListNode two = new ListNode(2, three);
        ListNode one = new ListNode(1, two);

        ListNode head = removeNthFromEnd(one, 2);
        ListNode node = head;
        while (node != null) {
            System.out.println(node.val + "→");
            node = node.next;

        }

    }
}

/**/
//  Definition for singly-linked list.
class ListNode {
    public int val;
    public ListNode next;

    ListNode() {
    }

    ListNode(int[] arr) {
        this.val = arr[0];
        ListNode pref = this;
        for (int i = 1; i < arr.length; i++) {
            pref.next = new ListNode(arr[i]);
            pref = pref.next;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        ListNode node = this;
        ListNode head = this;
        while (node != null) {
            sb.append(node.val).append("→");
            node = node.next;
            if (node == head) {
                break;
            }
        }
        if (sb.length() > 0) {
            sb.setLength(sb.length()-1);
        }
        sb.append("→ ");
        return sb.toString();
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

